package com.culture.bootdemo.算法.sort;

import java.util.Arrays;

/**
 * @Author: wen
 * @DateTime: 2024-11-22 10:28
 * @Description:
 **/
public class KuaiSuSort2 {
    // 主方法：用于调用快速排序方法
    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
    /* 快速排序 */
    public static void quickSort(int[] nums, int left, int right) {
        // 子数组长度为 1 时终止递归
        if (left >= right)
            return;
        // 哨兵划分
        int pivot = partition(nums, left, right);
        // 递归左子数组、右子数组
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    /* 哨兵划分 */
    public static int partition(int[] nums, int left, int right) {
        // 以 nums[right] 为基准数
        int pivot = nums[right];  // 基准值
        int i = left, j = right - 1; // 左右指针，注意 j 初始化为 right - 1

        while (i <= j) { // 循环直到 i 和 j 相遇
            while (i <= j && nums[i] <= pivot)
                i++;  // 从左向右找首个大于基准值的元素
            while (i <= j && nums[j] >= pivot)
                j--;  // 从右向左找首个小于基准值的元素
            if (i < j)
                swap(nums, i, j); // 交换这两个元素
        }
        swap(nums, i, right);  // 将基准值交换至分界线
        return i;              // 返回基准值的索引
    }

    /* 元素交换 */
    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


}
